import collections
from typing import List


class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)

        # 定义状态矩阵：dp[i][j] = 在点i时，已访问情况为j的最小移动步数
        dp = [[100] * pow(2, n) for _ in range(12)]

        # 完成时候的访问情况
        finish = (1 << n) - 1

        # 当前队列
        queue = collections.deque()

        for i in range(n):
            visited = (1 << i)
            dp[i][visited] = 0
            queue.append((i, visited))

        while queue:
            i1, v1 = queue.popleft()
            for i2 in graph[i1]:
                v2 = v1 | (1 << i2)
                if v2 == finish:
                    return dp[i1][v1] + 1
                if dp[i2][v2] > dp[i1][v1] + 1:
                    dp[i2][v2] = dp[i1][v1] + 1
                    queue.append((i2, v2))

        return 0  # 当没有结点时


if __name__ == "__main__":
    # 4
    print(Solution().shortestPathLength([[1, 2, 3], [0], [0], [0]]))

    # 4
    print(Solution().shortestPathLength([[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]]))
